1083. Sequence

Given a numerical sequence a₁, a₂, a₃, ...  the first term is known, and each subsequent term is calculated using the following formula:

a_i = (a_i-1 * a_i-1) mod 10000

Find the n-th term of this sequence.

Input. The first line contains two integers a₁ and n (0 ≤ a₁ ≤ 10000, 1 ≤ n ≤ 2000000010).

Output. Print the value of a_n.

Sample input	Sample output
4 3	256

SOLUTION

exponentiation

Algorithm analysis

Let us express the first terms of the sequence in terms of a₁:

· a₂ = a₁² mod 10000,

· a₃ = a₂² mod 10000 = a₁⁴ mod 10000,

· a₄ = a₃² mod 10000 = a₂⁴ mod 10000 = a₁⁸ mod 10000

Thus, the formula can be written as:

a_i = a_i-1² mod 10000

Which means that to compute a_n, it is enough to raise a₁ to the power of 2^n–1 modulo 10000:

Taking into account the modular exponentiation identity:

a^b mod n = a^{b mod j(n)} mod n,

we proceed as follows to find the result res:

· Compute x = 2^n–1 mod j(10000) = 2^n–1 mod 4000,

· Then compute res = a₁^x mod 10000

Algorithm implementation

The function PowMod computes the value of xⁿ mod m.

int PowMod(int x, int n, int m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

Read the input data.

scanf("%d %d",&a,&n);

Compute x = 2^n–1 mod 4000. And after that, compute and print the final answer:

res = a^x mod 10000

x = PowMod(2,n-1,4000);

res = PowMod(a,x,10000);

printf("%d\n",res);

Java implementation

import java.util.*;

public class Main

{

static long PowMod(long x, long n, long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long a = con.nextLong();

long n = con.nextLong();

long x = PowMod(2,n-1,4000);

long res = PowMod(a,x,10000);

System.out.println(res);

con.close();

}

}